1. Field of the Invention
The present invention relates to the field of integrated circuit design, more specifically, the verification of integrated circuit design. In particular, the present invention relates to the analysis and verification of finite state machines embedded in very large scale integrated circuit designs.
2. Background
Finite state machines (FSMs) are an integral part of any logic circuit. They are typically used in control logic, where the output depends not only on the current input to the circuit, but on the cumulative effect of all previous inputs. An FSM, therefore, can be considered as an abstract model describing a synchronous sequential machine. In this model, the effect of all previous inputs on the output is described by the present state or current state of the machine. In other words, if I is the set of possible input combinations, Z is the set of possible outputs, and Q is the set of possible states, then whenever I.sub.j eI is applied when the machine is in a state Q.sub.l eQ, the output Z.sub.k eZ is generated and the machine goes to state Q.sub.m eQ, where both Z.sub.k and Q.sub.m are uniquely determined by I.sub.j and Q.sub.l.
FSMs are typically used to implement complex decision sequences, and can therefore be very difficult to validate, particularly after they are embedded as part of a very large integrated circuit design. There are two basic problems to be addressed in the verification of finite state machines. The first problem deals with design verification and the second one deals with implementation verification. Design verification addresses the issue of whether the system has been correctly specified. This can only be done through simulation of a model of the entire logic circuit. Typically, a High-level Design Language (HDL) is used to model the logic circuit and functional/diagnostic tests are developed to exercise the circuit design using a simulator. Thus, it is often difficult if not outright impossible to verify the design of FSMs. Therefore, it is desirable to be able to analyze and verify FSMs even after they are embedded as part of a very large integrated circuit. Implementation verification on the other hand, attempts to compare the HDL description with its implementation. With advances in synthesis algorithms, implementation verification is becoming less important since the synthesized implementation is typically correct by construction. Nevertheless, it is still desirable to be able to verify the implementation of FSMs. As will be disclosed, the present invention provides a state machine transition analyzer that advantageously allow verification of the design and implementation of FSMs.